کد های کشف و تصحیح خطا در شبکه
خطا در انتقال داده به مفهوم تشخیص نادرست بیت ارسالی در گیرنده است (برای مثال بیت صفر ارسال شده را در گیرنده یک تشخیص دهیم).
منظور از کنترل خطا ، امور مربوط به شناسایی یا تشخیص خطا ( کشف وجودخطا(Error Detection )) و تصحیح آن (کشف موقعیت بیت خطا( Error Correction ))می باشد.
به طور کلی دو روش برای کنترل خطا وجود دارد:
پیش رو Forward Error Correction : FEC : در این روش داده های افزونه به همراه اطلاعات اصلی به گیرنده ارسال می شود. این افزونگی(Redundancy )برای تشخیص و تصحیح خطا در گیرنده به کار می رود.
پس رو Feedback ( Backward ) Error Correction : در این روش ، افزونگی فقط می تواند به گیرنده در تشخیص وجود خطا کمک کند و اطلاعات دارای خطا باید دوباره ارسال شود.
فرض کنید یک داده (فریم یا کاراکتر ) را باید ارسال نماییم. اگر طول ناحیه داده اصلی برابر m بیت واطلاعات افزونه ( برای تشخیص و یا تصحیح خطا ) برابر r بیت باشد ، طول کل فریم (کد) برابر (m+r ) خواهد بود.
Hamming Distance
فاصله همینگ (D ) بین دو کدC1,C2 برابر تعداد بیت های متفاوت در آن دو کد است.
مثال: اگر C1=1 0 0 1 0 0 و C2=1 0 1 0 1 0 باشد ، فاصله همینگ C1,C2عبارت است از:
D( C1, C2 )==3
وزن (Weight ) یک کد برابر تعداد یک های آن کد است :
W(C1)=2 , W(C2)=3
نکته 1: فاصله همینگ مجموعه ای از کدها ، برابر حداقل فاصله همینگ بین اعضائ مجموعه می باشد .
مثال: برای مجموعه کدهای {0011 , 0001 , 1100 } ، فاصله همینگ را محاسبه کنید.
C1=0011
C2=0001
C3=1100
D(C1,C2)=1
D(C1,C2)=4
D=(C1,C2)=3
D=Min{1,2,3}=1
نکته 2: اگر فاصله همینگ در یک مجموعه کد ، برابر 5 باشد . چند بیت خطا قابل تشخیص است ؟
فرض کنید حداقل فاصله همینگ مربوط به دو کد C2 , C1از این مجموعه باشد. بنابر این همانطور که در شکل 44 دیده می شود ، ممکن است با رخداد پنج خطا ، کد C1 به کد C2که هر دو مجاز هستند تبدیل شود و تشخیص غیر ممکن شود .
اگر یک یا دو خطا رخ دهد ، کد غیر مجازی بوجود می آید که به کد مجاز اولیه از سایر کدها ی مجاز نزدیکتر (Dmin ) است وعلاوه بر تشخیص خطا ، تصحیح نیز صورت می گیرد وکد اولیه به عنوان کد صحیح انتخاب می شود. اما اگر سه خطا رخ دهد ، فاصله همینگ کد حاصل با یک کد مجاز دیگر ، کمتر از فاصله همینگ آن با کد صحیح اولیه است و لذا منجر به خطا خواهد شد.
· دو بیت خطا قابل تشخیص است، اما چون فاصله همینگ از دو طرف برابر است عمل تصحیح غیر ممکن خواهد بود.
· سه خطا منجر به تصحیح نادرست می شود.
کد افزونگی چرخشیCRC
یک کد افزونگی چرخشی (به انگلیسی: Cyclic redundancy code) (سی‌آرسی) تابع درهم‌سازی غیرایمنی است که جهت تشخیص تغییرات تصادفی رو داده‌های خام طراحی شده‌است. این تابع عموما در شبکه‌های مخابراتی دیجیتال و وسایل ذخیره‌سازی داده‌ها از جمله دیسک سخت مورد استفاده قرار میگیرد. یک دستگاه دارای قابلیت سی‌آرسی، یک توالی کوتاه و با طول ثابت را، به نام کد سی‌آرسی (یا فقط سی‌آرسی)، برای هر بلاک از داده‌ها محاسبه نموده و آن را همراه با داده‌ها ذخیره یا ارسال می‌کند. زمانی که یک بلاک دریافت یا خوانده می‌شود دستگاه محاسبه را تکرار می‌کند؛ در صورت مغایرت با کد محاسبه شده قبلی مشخص می‌شود که این بلاک دارای خطای داده است و در این حالت دستگاه ممکن است عملی را جهت اصلاح خطا از جمله خواندن یا درخواست ارسال مجدد بلاک انجام دهد. اصطلاح سی‌آرسی می‌تواند به کد اعتبارسنج یا تابع تولید کد اطلاق شود. سی‌آرسی‌ها به جهت پیاده‌سازی ساده در سخت‌افزار دودویی، سادگی تحلیل ریاضی آن‌ها و عملکرد خوب در تشخیص خطاهای معمول حاصل از اختلال در کانال‌های انتقال دارای محبوبیت زیادی هستند. سی‌آرسی توسطW. Wesley Petersonاختراع و در مقاله ۱۹۶۱ وی منتشر شد . سی‌آرسی 32 بیتی پیشنهادی موسسه مهندسین الکتریک و الکترونیک (IEEE)، که در اترنت و سایر جاها استفاده شده‌است، در کنفرانس مخابراتی سال 1975 ظاهر شد.
سی‌آرسی یک کد تشخیص خطا است. محاسبه آن شبیه عمل تقسیم اعشاری است که خارج قسمت حذف می‌شود و باقیمانده به عنوان نتیجه در نظر گرفته می‌شود، با این تفاوت مهم که محاسبات آن محاسبات بدون رقم نقلی از یک میدان محدود است. اعلام یک سی‌آرسی خاص با مشخص کردن مقسم و سایر مشخصات آن انجام می‌شود.
اگرچه سی‌آرسی‌ها می‌توانند با استفاده از هر میدان محدودی ساخته شوند، همه سی‌آرسی‌های پرکاربرد از میدان محدودGF(2) بهره می‌برند. این میدانی از دو عنصر، عموما به نام ۰ و ۱، است که به راحتی با معماری کامپیوتر سازگار است. یک دلیل مهم برای محبوبیت سی‌آرسی‌ها برای تشخیص تغییرات تصادفی داده‌ها اطمینان از کیفیت آن‌ها است. نوعا"، یک سی‌آرسی nبیتی، که برای یک بلاک داده با طول دلخواه محاسبه شده‌است، هر حوزه خطای با طول کمتر از n بیت (به عبارت دیگر، هر تغییری که محدوده آن بیش از n بیت مجاور از داده‌ها نباشد) و 1-2^(-n) تعداد از سایر حوزه‌های با طول بیش از n بیت را تشخیص می‌دهد. خطاها در هیچ‌یک از کانال‌های انتقال و رسانه‌های ذخیره‌سازی مغناطیسی دارای توزیع تصادفی نیستند و در نتیجه فایده خواص سی‌آرسی‌ها را نسبت به سایر روش‌های تشخیص خطا از جمله کدهای چندگانه زوجیت بیشتر می‌کنند. ساده‌ترین سامانه تشخیص خطا، بیت زوجیت، در واقع یک سی‌آرسی عادی است که از مقسم دوبیتی ۱۱ استفاده می‌کند.
کد گری
انگیزه پیدایش کد گری
بعضی از دستگاه‌ها وضعیت دستگاه را با کدهای باینری نمایش می‌دهند، اگر این دستگاه‌ها از کد باینری عادی استفاده کند این دو وضعیت پشت سر هم خواهند بود 011 -- > 100 و مشکل کد باینری عادی این است که در حالت طبیعی خیلی بعید نست که چند بیت همزمان تغییر کنند همان طور که در بالا نمایش داده شده‌است که در کد باینری عادی هر سه بیت همزمان تغییر کرده‌اند اما می‌توان اعداد را طوری در کنار هم قرار داد که فقط در یک بیت متفاوت باشند و تغییر زیادی نکنند مثلا" 011 − 001 − 101 − 100 پس کد باینری منعکس شده یا همان کد گری این مشکل را حل می‌کند زیرا که فقط یک بیت در آن‌ها تغییر می‌کند.
:: بازدید از این مطلب : 18493
|
امتیاز مطلب : 12
|
تعداد امتیازدهندگان : 3
|
مجموع امتیاز : 3
عضو شوید
عضویت سریع
آمار
وب سایت:
آمار مطالب
آمار بازدید
